package algorithms;

public final class HeapSorter {
	
	public static<T extends Comparable<T>> void sort(T[] inArray){
		if( inArray.length < 2 )
			return;
		int n0 = inArray.length/2 - 1;
		for( int i = n0; i >= 0; i-- )
			sieveDown(inArray, i, inArray.length);
		
		int nLast = inArray.length - 1;
		while( nLast > 0 ){
			swap(inArray, 0, nLast);
			sieveDown(inArray, 0, nLast);
			nLast--;
		}
	}
	
	static<T extends Comparable<T>> void sieveDown(T[] inArray, int index, int Top){
		while( index*2 < Top || index*2 + 1 < Top ){
			int newIndex = index*2;
			if( newIndex + 1 == Top ){
				if( inArray[newIndex].compareTo(inArray[index]) > 0 )
					swap(inArray, index, newIndex);
				return;
			}
			if( inArray[newIndex +1].compareTo(inArray[newIndex]) > 0 )
				newIndex++;
			if( inArray[index].compareTo(inArray[newIndex]) >= 0 )
				return;
			
			swap(inArray, index, newIndex);
			index = newIndex;
		}
	}
	
	static<T> void swap(T[] inArray, int index1, int index2){
		T tmp = inArray[index1];
		inArray[index1] = inArray[index2];
		inArray[index2] = tmp;
	}

}
